Due to the presence of noise on a communications channel, the signal received is not always identical to the signal transmitted. Channel coding, or equivalently, error correction coding, relates to techniques for increasing the probability that a receiver in a communications systems will be able to correctly detect the composition of the transmitted data stream. Typically, this is accomplished by encoding the signal to add redundancy before it is transmitted. This redundancy increases the likelihood that the receiver will be able to correctly decode the encoded signal and recover the original data.
Turbo coding, a relatively new but widely used channel coding technique, has made signaling at power efficiencies close to the theoretical limits possible. The features of a turbo code include parallel code concatenation, non-uniform interleaving, and iterative decoding. Because turbo codes may substantially improve energy efficiency, they are attractive for use over channels that are power and/or interference limited.
A turbo decoder may be used to decode the turbo code. The turbo decoder may include two soft-input/soft-output (SISO) decoding modules that work together in an iterative fashion.
The SISO decoding module is the basic building block for established iterative detection techniques for a system having a network of finite state machines, or more generally, subsystems.
FIGS. 7A and 7B respectively show block diagrams of typical turbo encoder 10 and turbo decoder 11 arrangements. In this example, the turbo encoder 10 uses two separate encoders, RSC1 and RSC2, each a Recursive Systematic Convolutional encoder. Each of the encoders RSC1 and RSC2 can be modeled as a finite state machine (FSM) having a certain number of states (typically, either four or eight for turbo encoders) and transitions therebetween. To encode a bit stream for transmission over a channel, uncoded data bits bk are input both to the first encoder RSC1 and an interleaver I. The interleaver I shuffles the input sequence bk to increase randomness and introduces the shuffled sequence ak to the second decoder RSC2. The outputs of encoders RSC1 and RSC2, ck and dk respectively, are punctured and modulated by block 12 to produced encoded outputs xk(0) and xk(1), which are transmitted over a channel to the decoder 11.
At the decoder 11, the encoded outputs are received as noisy inputs zk(0) and zk(1) and are de-modulated and de-punctured by block 13, which is the soft-inverse of puncture and modulation block 12. The output of block 13, M[ck(0)], M[ck(1)] and M[dk(1)], is “soft” information—that is, guesses or beliefs about the most likely sequence of information bits to have been transmitted in the coded sequences ck(0), ck(1) and dk(1), respectively. The decoding process continues by passing the received soft information M[ck(0)], M[ck(1)] to the first decoder, SISO1, which makes an estimate of the transmitted information to produce soft output M[bk] and passes it to interleaver I (which uses the same interleaving mapping as the interleaver I in the encoder 10) to generate M[ak]. The second decoder, SISO2, uses M[ak] and received soft information M[dk(1)] to re-estimate the information. This second estimation is looped back, via the soft inverse of the interleaver, I−1, to SISO1 where the estimation process starts again. The iterative process continues until certain conditions are met, such as a certain number of iterations are performed, at which point the final soft estimates become “hard” outputs representing the transmitted information.
Each of the SISO decoder modules in the decoder 11 is the soft-inverse of its counterpart RSC encoder in the encoder 10. The conventional algorithm for computing the soft-inverse is known as the “forward-backward” algorithm such as described in G. David Forney, Jr., “The Forward-Backward Algorithm,” Proceedings of the 34th Allerton Conference on Communications, Control and Computing, pp. 432–446 (October 1996). In the forward-backward algorithm, an estimate as to a value of a data bit is made by recursively computing the least cost path (using add-compare-select, or ACS, operations) forwards and backwards through the SISO's “trellis”—essentially an unfolded state diagram showing all possible transitions between states in a FSM. Each path through the SISO's trellis has a corresponding cost, based on the received noisy inputs, representing a likelihood that the RSC took a particular path through its trellis when encoding the data. Typically, the lower a path's total cost, the higher the probability that the RSC made the corresponding transitions in encoding the data. In general, the forward and backward ACS recursions performed by a SISO can be computed either serially or in parallel. Performing the recursions in parallel, the faster of the two methods, yields an architecture with latency O(N), where N is the block size of the encoded data. As used herein, “latency” is the end-to-end delay for decoding a block of N bits.
The present inventors recognized that, depending on the latency of other components in a decoder or other detection system, reducing the latency of a SISO could result in a significant improvement in the system's throughput (a measurement of the number of bits per second that a system architecture can process). Consequently, the present inventors developed a tree-structured SISO that can provide reduced latency.